---
title: "Algorithms and Data Structures"
description: "Learn C algorithms and data structures from a JavaScript perspective. Understand arrays, linked lists, sorting, searching, and compare with JavaScript data structures."
---

# Algorithms and Data Structures

## 1. Introduction

### From JavaScript Data Structures to C Implementations

In JavaScript, you have built-in arrays, objects, and high-level data structures. In C, you must implement data structures from scratch, giving you complete control over memory layout and performance characteristics.

> 💡 **Key Concept**: C implementations of data structures provide maximum performance and memory efficiency, but require careful memory management and algorithm design.

## 2. Linear Data Structures

<UniversalEditor title="Arrays and Dynamic Arrays" compare={true}>
```javascript !! js
// JavaScript - built-in arrays
let arr = [1, 2, 3, 4, 5];

// Array operations
arr.push(6);           // Add to end
arr.unshift(0);        // Add to beginning
arr.pop();             // Remove from end
arr.shift();           // Remove from beginning
arr.splice(2, 1);      // Remove at index 2

// Array iteration
for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
}

// Array methods
arr.forEach(item => console.log(item));
arr.map(item => item * 2);
arr.filter(item => item > 3);
arr.reduce((sum, item) => sum + item, 0);

// Dynamic array behavior
console.log("Array length:", arr.length);
arr[10] = 100; // Automatically expands
console.log("New length:", arr.length);
```

```c !! c
#include <stdio.h>
#include <stdlib.h>

// Dynamic array structure
typedef struct {
    int* data;
    int size;
    int capacity;
} DynamicArray;

// Initialize dynamic array
DynamicArray* createArray(int initialCapacity) {
    DynamicArray* arr = (DynamicArray*)malloc(sizeof(DynamicArray));
    arr->data = (int*)malloc(initialCapacity * sizeof(int));
    arr->size = 0;
    arr->capacity = initialCapacity;
    return arr;
}

// Add element to end
void push(DynamicArray* arr, int value) {
    if (arr->size >= arr->capacity) {
        // Resize array
        arr->capacity *= 2;
        arr->data = (int*)realloc(arr->data, arr->capacity * sizeof(int));
    }
    arr->data[arr->size++] = value;
}

// Remove element from end
int pop(DynamicArray* arr) {
    if (arr->size > 0) {
        return arr->data[--arr->size];
    }
    return -1; // Error value
}

// Get element at index
int get(DynamicArray* arr, int index) {
    if (index >= 0 && index < arr->size) {
        return arr->data[index];
    }
    return -1; // Error value
}

// Free array memory
void freeArray(DynamicArray* arr) {
    free(arr->data);
    free(arr);
}

int main() {
    DynamicArray* arr = createArray(5);
    
    // Add elements
    push(arr, 1);
    push(arr, 2);
    push(arr, 3);
    push(arr, 4);
    push(arr, 5);
    
    // Print array
    printf("Array: ");
    for (int i = 0; i < arr->size; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");
    
    // Remove element
    int removed = pop(arr);
    printf("Removed: %d\n", removed);
    
    // Print updated array
    printf("Updated array: ");
    for (int i = 0; i < arr->size; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");
    
    freeArray(arr);
    return 0;
}
```
</UniversalEditor>

## 3. Linked Lists

<UniversalEditor title="Linked Lists" compare={true}>
```javascript !! js
// JavaScript - linked list implementation
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    
    // Add to end
    append(data) {
        const newNode = new Node(data);
        
        if (!this.head) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.size++;
    }
    
    // Add to beginning
    prepend(data) {
        const newNode = new Node(data);
        newNode.next = this.head;
        this.head = newNode;
        this.size++;
    }
    
    // Remove element
    remove(data) {
        if (!this.head) return;
        
        if (this.head.data === data) {
            this.head = this.head.next;
            this.size--;
            return;
        }
        
        let current = this.head;
        while (current.next && current.next.data !== data) {
            current = current.next;
        }
        
        if (current.next) {
            current.next = current.next.next;
            this.size--;
        }
    }
    
    // Print list
    print() {
        let current = this.head;
        while (current) {
            console.log(current.data);
            current = current.next;
        }
    }
}

// Usage
const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.prepend(0);
list.print();
```

```c !! c
#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Linked list structure
typedef struct {
    Node* head;
    int size;
} LinkedList;

// Create new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Initialize linked list
LinkedList* createLinkedList() {
    LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
    list->head = NULL;
    list->size = 0;
    return list;
}

// Add to end
void append(LinkedList* list, int data) {
    Node* newNode = createNode(data);
    
    if (list->head == NULL) {
        list->head = newNode;
    } else {
        Node* current = list->head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
    list->size++;
}

// Add to beginning
void prepend(LinkedList* list, int data) {
    Node* newNode = createNode(data);
    newNode->next = list->head;
    list->head = newNode;
    list->size++;
}

// Remove element
void removeElement(LinkedList* list, int data) {
    if (list->head == NULL) return;
    
    if (list->head->data == data) {
        Node* temp = list->head;
        list->head = list->head->next;
        free(temp);
        list->size--;
        return;
    }
    
    Node* current = list->head;
    while (current->next != NULL && current->next->data != data) {
        current = current->next;
    }
    
    if (current->next != NULL) {
        Node* temp = current->next;
        current->next = current->next->next;
        free(temp);
        list->size--;
    }
}

// Print list
void printList(LinkedList* list) {
    Node* current = list->head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// Free list memory
void freeList(LinkedList* list) {
    Node* current = list->head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    free(list);
}

int main() {
    LinkedList* list = createLinkedList();
    
    append(list, 1);
    append(list, 2);
    append(list, 3);
    prepend(list, 0);
    
    printf("Original list: ");
    printList(list);
    
    removeElement(list, 2);
    printf("After removing 2: ");
    printList(list);
    
    freeList(list);
    return 0;
}
```
</UniversalEditor>

## 4. Sorting Algorithms

<UniversalEditor title="Sorting Algorithms" compare={true}>
```javascript !! js
// JavaScript - built-in sort
let arr = [64, 34, 25, 12, 22, 11, 90];
arr.sort((a, b) => a - b);
console.log("Sorted:", arr);

// Bubble sort implementation
function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

// Quick sort implementation
function quickSort(arr) {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[Math.floor(arr.length / 2)];
    const left = arr.filter(x => x < pivot);
    const middle = arr.filter(x => x === pivot);
    const right = arr.filter(x => x > pivot);
    
    return [...quickSort(left), ...middle, ...quickSort(right)];
}

// Test sorting
let testArr = [64, 34, 25, 12, 22, 11, 90];
console.log("Original:", testArr);
console.log("Bubble sort:", bubbleSort([...testArr]));
console.log("Quick sort:", quickSort([...testArr]));
```

```c !! c
#include <stdio.h>
#include <stdlib.h>

// Swap function
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Bubble sort
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

// Quick sort partition
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

// Quick sort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Print array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array: ");
    printArray(arr, n);
    
    // Bubble sort
    int bubbleArr[7];
    for (int i = 0; i < n; i++) {
        bubbleArr[i] = arr[i];
    }
    bubbleSort(bubbleArr, n);
    printf("Bubble sorted: ");
    printArray(bubbleArr, n);
    
    // Quick sort
    int quickArr[7];
    for (int i = 0; i < n; i++) {
        quickArr[i] = arr[i];
    }
    quickSort(quickArr, 0, n - 1);
    printf("Quick sorted:  ");
    printArray(quickArr, n);
    
    return 0;
}
```
</UniversalEditor>

## 5. Search Algorithms

<UniversalEditor title="Search Algorithms" compare={true}>
```javascript !! js
// JavaScript - built-in search methods
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

// Linear search
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

// Binary search (requires sorted array)
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// Test search algorithms
console.log("Array:", arr);
console.log("Linear search for 7:", linearSearch(arr, 7));
console.log("Binary search for 7:", binarySearch(arr, 7));
console.log("Linear search for 11:", linearSearch(arr, 11));
console.log("Binary search for 11:", binarySearch(arr, 11));
```

```c !! c
#include <stdio.h>

// Linear search
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

// Binary search (requires sorted array)
int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// Print search result
void printSearchResult(int result, int target) {
    if (result != -1) {
        printf("Found %d at index %d\n", target, result);
    } else {
        printf("%d not found in array\n", target);
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    // Test linear search
    int target1 = 7;
    int result1 = linearSearch(arr, n, target1);
    printf("Linear search: ");
    printSearchResult(result1, target1);
    
    // Test binary search
    int target2 = 7;
    int result2 = binarySearch(arr, 0, n - 1, target2);
    printf("Binary search: ");
    printSearchResult(result2, target2);
    
    // Test not found
    int target3 = 11;
    int result3 = linearSearch(arr, n, target3);
    printf("Linear search: ");
    printSearchResult(result3, target3);
    
    return 0;
}
```
</UniversalEditor>

## 6. Common Pitfalls
- **Memory leaks**: Always free allocated memory in data structures
- **Buffer overflows**: Check array bounds before accessing elements
- **Null pointer dereference**: Always check for NULL pointers
- **Algorithm complexity**: Be aware of time and space complexity
- **Data structure choice**: Choose appropriate structure for the problem

## 7. Exercises
1. Implement a stack data structure using arrays or linked lists.
2. Write a function to reverse a linked list iteratively and recursively.
3. Implement merge sort and compare its performance with quick sort.
4. Create a hash table implementation with collision resolution.

## 8. Performance Analysis
- **Arrays**: O(1) access, O(n) insertion/deletion
- **Linked Lists**: O(n) access, O(1) insertion/deletion at ends
- **Bubble Sort**: O(n²) time complexity
- **Quick Sort**: O(n log n) average, O(n²) worst case
- **Linear Search**: O(n) time complexity
- **Binary Search**: O(log n) time complexity

---

> **Summary**: C implementations of algorithms and data structures provide maximum control and performance. Understanding memory management, algorithm complexity, and choosing appropriate data structures is crucial for efficient C programming. 